/*
 * One example for NOI CSP-J Lesson 6:
 * <https://courses.fmsoft.cn/plzs/noijunior-search-algorithms.html>
 *
 * Author: Vincent Wei
 *  - <https://github.com/VincentWei>
 *  - <https://gitee.com/vincentwei7>
 *
 * Copyright (C) 2025 FMSoft <https://www.fmsoft.cn>.
 * License: GPLv3
 */
#include <iostream>     // std::cout
#include <algorithm>    // std::lower_bound, std::upper_bound, std::binary_search, std::sort
#include <random>       // std::default_random_engine
#include <vector>       // std::vector
#include <cassert>      // assert()

int main ()
{
    int myints[] = {10,20,30,30,20,10,10,20};
    std::vector<int> v(myints, myints+8);           // 10 20 30 30 20 10 10 20

    // 在无序线性容器上执行二分搜索可能获得错误结果
    std::cout << "looking for a 30... ";
    if (std::binary_search(v.begin(), v.end(), 30))
        std::cout << "found!\n";
    else
        std::cout << "not found.\n";

    // 默认为升序排序
    std::sort(v.begin(), v.end());                  // 10 10 10 20 20 20 30 30
    assert(v[0] == 10);

    // 注意：std::lower_bound 和 std::upper_bound 的
    // 返回值类型为前向迭代子（iterator）
    std::vector<int>::iterator low, up;
    low = std::lower_bound(v.begin(), v.end(), 20); //          ^
    up  = std::upper_bound(v.begin(), v.end(), 20); //                   ^

    // 迭代子上的减法运算将得到偏移量
    std::cout << "lower_bound at position " << (low - v.begin()) << std::endl;
    std::cout << "upper_bound at position " << (up  - v.begin()) << std::endl;

    // std::binary_search() 函数的返回值类型为 bool
    std::cout << "looking for a 30... ";
    if (std::binary_search(v.begin(), v.end(), 30))
        std::cout << "found!\n";
    else
        std::cout << "not found.\n";

    // 这里调用 cstdlib 中暴露的 C 函数 time()，用其返回值做随机数种子。
    std::shuffle(v.begin(), v.end(),
            std::default_random_engine((unsigned)time(NULL)));

    // 重载 compareLess 的 () 运算符，则 compareLess 实例上的 () 运算符
    // 可作为 std::sort()、std::lower_bound(), std::uppper_bound() 的定制
    // Compare 参数。
    // 注意用作对比的函数返回值类型为 bool。
    struct compareLess {
        bool operator()(int a, int b) {
            return a > b;           // 使用该逻辑将执行降序排序。
        }
    };

    struct compareLess mycomp{};
    std::sort(v.begin(), v.end(), mycomp);
    assert(v[0] == 30);

    std::cout << "looking for a 20... ";
    if (std::binary_search (v.begin(), v.end(), 20, mycomp))
        std::cout << "found!\n";
    else
        std::cout << "not found.\n";

    return 0;
}
